1550. Битовые уравнения

Вам заданы два натуральных числа x и k. Найдите k-ое наименьшее натуральное решение y (значение k считается с 1) следующего уравнения:

x + y = x | y

Через '|' здесь обозначена побитовая операция OR.

Вход. Каждая строка является отдельным тестом и содержит два целых числа x и k (1 ≤ x, k ≤ 2*10⁹).

Выход. Для каждого теста в отдельной строке вывести k-ое наименьшее натуральное решение y выше приведенного уравнения.

Пример входа

5 1

5 5

10 3

1 1000000000

Пример выхода

2

18

5

2000000000

РЕШЕНИЕ

математика

Анализ алгоритма

Значение y будет решением уравнения тогда и только тогда, когда y имеет нули в тех позициях, в которых в x стоят единицы. Например, если x = 1001101001₂ = 617₁₀, то последние 10 цифр y должны быть 0**00*0**0, где ‘*’ обозначает 0 или 1. Любая замена звездочек на 0 или 1 дает решение. Наименьшим будет решение, когда звездочки будут заменены на 00001, то есть y = 0000000010 = 10₂ = 2₁₀, x + y = x | y = 1001101011₂ = 619₁₀. Второе наименьшее решение получится, если звездочки заменить на 00010, третье – если на 00011 и так далее.

k - ое наименьшее положительное целое решение уравнения можно получить, если звездочки заменить на двоичное представление числа k.

Реализация алгоритма

Функция kthPlusOrSolution возвращает k - ое наименьшее натуральное решение уравнения.

long long kthPlusOrSolution(long long x, long long k)

{

long long pos, y = 0;

for(pos = 0; k; pos++)

{

Если в бинарном представлении числа x в позиции pos стоит 1, то в y на этой позиции должен находиться 0.

if (x >> pos & 1) continue;

В позицию pos результата y заносим последний бит числа k. Далее делим k на 2, таким образом перебирая все биты его двоичного представления.

if (k % 2) y = y | (1LL << pos);

k /= 2;

}

return y;

}

Основная часть программы.

while(scanf("%lld %lld",&x,&k) == 2)

{

res = kthPlusOrSolution(x,k);

printf("%lld\n",res);

}